package ricky.quadtree
{
	import flash.geom.Rectangle;

	/**
	 * 线性四叉树节点
	 */
	public class Node
	{

		function Node(bounds:Rectangle, depth, maxDepth:int=NaN, maxChildren:int=NaN)
		{
			this._bounds = bounds;
			this.children = [];
			this.nodes = [];
			
			if(maxChildren)
			{
				this._maxChildren = maxChildren;
				
			}
			
			if(maxDepth)
			{
				this._maxDepth = maxDepth;
			}
			
			if(depth)
			{
				this._depth = depth;
			}
		}
		
		//subnodes
		public var  nodes:Array = null;
		protected var  _classConstructor:Class = Node;
		
		//children contained directly in the node
		protected var  children:Array = null;
		public var  _bounds:Rectangle = null;
		
		//read only
		protected var  _depth = 0;
		
		protected var  _maxChildren = 4;
		protected var  _maxDepth = 4;
		
		public static const TOP_LEFT:int = 0;
		public static const TOP_RIGHT:int = 1;
		public static const BOTTOM_LEFT:int = 2;
		public static const BOTTOM_RIGHT:int= 3;
		
		
		public function insert(item)
		{
			if(this.nodes.length)
			{
				var index = this._findIndex(item);
				
				this.nodes[index].insert(item);
				
				return;
			}
			
			this.children.push(item);
			
			var len = this.children.length;
			if(!(this._depth >= this._maxDepth) && 
				len > this._maxChildren)
			{
				this.subdivide();
				
				for(var i = 0; i < len; i++)
				{
					this.insert(this.children[i]);
				}
				
				this.children.length = 0;
			}
		}
		
		public function retrieve(item)
		{
			if(this.nodes.length)
			{
				var index = this._findIndex(item);
				
				return this.nodes[index].retrieve(item);
			}
			
			return this.children;
		}
		
		public function _findIndex(item)
		{
			var b = this._bounds;
			var left = (item.x > b.x + b.width / 2)? false : true;
			var top = (item.y > b.y + b.height / 2)? false : true;
			
			//top left
			var index = Node.TOP_LEFT;
			if(left)
			{
				//left side
				if(!top)
				{
					//bottom left
					index = Node.BOTTOM_LEFT;
				}
			}
			else
			{
				//right side
				if(top)
				{
					//top right
					index = Node.TOP_RIGHT;
				}
				else
				{
					//bottom right
					index = Node.BOTTOM_RIGHT;
				}
			}
			
			return index;
		}
		
		public function clear()
		{	
			this.children.length = 0;
			
			var len = this.nodes.length;
			for(var i = 0; i < len; i++)
			{
				this.nodes[i].clear();
			}
			
			this.nodes.length = 0;
		}
		
		
		public function subdivide()
		{
			var depth = this._depth + 1;
			
			var bx = this._bounds.x;
			var by = this._bounds.y;
			
			//floor the values
			var b_w_h = (this._bounds.width / 2)|0;
			var b_h_h = (this._bounds.height / 2)|0;
			var bx_b_w_h = bx + b_w_h;
			var by_b_h_h = by + b_h_h;
			
			//top left
			this.nodes[Node.TOP_LEFT] = new this._classConstructor(new Rectangle(bx,by,b_w_h, b_h_h),depth);
			
			//top right
			this.nodes[Node.TOP_RIGHT] = new this._classConstructor(new Rectangle(bx_b_w_h,by,b_w_h,b_h_h),depth);
			
			//bottom left
			this.nodes[Node.BOTTOM_LEFT] = new this._classConstructor(new Rectangle(bx,by_b_h_h,b_w_h, b_h_h),depth);
			
			
			//bottom right
			this.nodes[Node.BOTTOM_RIGHT] = new this._classConstructor(new Rectangle(bx_b_w_h,by_b_h_h,b_w_h, b_h_h),depth);	
		}
		

	}
}

	